#ifndef GAMEENGINE_AI_NAVMESH_FUNNEL_H
#define GAMEENGINE_AI_NAVMESH_FUNNEL_H

#include <GameEngine/AI/ai_settings.h>

#include <list>
#include <vector>



#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=================================================================================

template <class Vertex> class Funnel;

//! Class used to handle triangle data in funnels
/*!
 *  The funnel triangle does not handle the memory associated to its vertices; the
 *  vertices should therefore not be deleted while the funnel triangle is still in
 *  use, otherwise the function calls are likely to result in an application crash.
 *
 *  This class is templated by the type of vertex to be used.
 */
template <class Vertex>
class FunnelTriangle {
	//! The funnel class is friend of the funnel triangle class to allow direct data access
	friend class Funnel<Vertex>;

public:
	FunnelTriangle();
	FunnelTriangle(const Vertex* v0, const Vertex* v1, const Vertex* v2);
	FunnelTriangle(const FunnelTriangle& rhs);
	~FunnelTriangle();
	FunnelTriangle& operator=(const FunnelTriangle& rhs);

	const Vertex* v0() const;
	const Vertex* v1() const;
	const Vertex* v2() const;

private:
	const Vertex* v0_;
	const Vertex* v1_;
	const Vertex* v2_;
};

//=================================================================================

//! Research of the shortest path in a funnel
/*!
 *  A funnel is a set of triangles, where triangle k is connected to triangles
 *  k-1 and k+1 only (see figure below).
 *
 @image html funnel.png "An example of a funnel. From Efficient Triangulation-Based Pathfinding, Demyen, 2007, page 53."
 *
 *  The funnel search algorithm allows to find the shortest path in a funnel
 *  with linear time, the performances being a function of the number of triangles
 *  in the funnel. A description of the funnel search algorithm can also be found
 *  in Demyen, 2007.
 *
 *  One of the interests of this class is to provide a cost heuristic with the A-star
 *  algorithm in navigation meshes. To be fully compatible with the implementation of
 *  A-star, the funnel class should rather be defined as a single-linked list.
 */
template <class Vertex>
class Funnel {

public:
	//! Typedef used to handle triangle data
	typedef FunnelTriangle<Vertex> Trgl;

public:
	static std::list<Vertex> find_path(const std::vector<Trgl>& trgl_funnel);
	static std::list<Vertex> find_path(const std::vector<Trgl>& trgl_funnel, float radius);

private:
	//! Handle the side of the funnel that is currently manipulated
	enum Side {
		//! Right side of the funnel
		RightSide,
		//! Left side of the funnel
		LeftSide,
		//! Start or end point of the funnel
		NoSide
	};

	//! Typedef used to handle oriented funnel points
	typedef std::pair< Vertex, Side > FunnelPoint;
	//! Typedef used to handle internal edge data
	typedef std::pair< const Vertex*, const Vertex* > InternalEdge;

private:
	static bool build_funnel(std::list< FunnelPoint >& pts, const Vertex* start, const Vertex* end, const std::vector<Trgl>& trgl_funnel);
	static bool build_funnel(std::list< FunnelPoint >& pts, float radius, const Vertex* start, const Vertex* end, const std::vector<Trgl>& trgl_funnel);
	static bool build_path(std::list< Vertex >& path, const std::list< FunnelPoint >& pts, const Vertex* end);

	static Side side(const Vertex& v0, const Vertex& v1, const Vertex& v2);
	static Side side(const Trgl& trgl);
	static bool common_vertices(InternalEdge& vertices, const Trgl& trgl1, const Trgl& trgl2);
	static const Vertex* opposite_vertex(const Trgl& trgl, const InternalEdge& edge);
	static const Vertex* opposite_vertex(const Trgl& trgl, const Trgl& other_trgl);
};

//=================================================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#include <GameEngine/AI/Navmesh/funnel.hpp>

#endif
